# leetcode submit region begin(Prohibit modification and deletion)
from typing import List


class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        k = len(nums) - 1
        while k > 0 and nums[k] < nums[k - 1]:
            k -= 1
        if k <= 0:
            nums.reverse()
        else:
            t = k
            while t < len(nums) and nums[t] > nums[k - 1]:
                t += 1
            nums[k-1], nums[t-1] = nums[t-1], nums[k-1]
            l, r = k, len(nums) - 1
            while l < r:
                nums[l], nums[r] = nums[r], nums[l]
                l += 1
                r -= 1


ns = [1, 2, 3]
Solution().nextPermutation(ns)
print(ns)
